home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Reference Guide / C-C++ Interactive Reference Guide.iso / c_ref / csource4 / 246_01 / cycle21.c < prev    next >
Text File  |  1987-10-29  |  5KB  |  266 lines
  1.  
  2.  
  3. /* CYCLE21.C                     */
  4. /* program to analyze the cycles of a cellular   */
  5. /* automaton and report all the periodic states. */
  6. /* [Harold V. McIntosh, 21 May 1987]         */
  7.  
  8. # include <stdio.h>
  9.  
  10. # define KK     2            /* number of states/cell    */
  11. # define NS      4            /* number of distinct sums    */
  12. # define NW    24            /* pause after so many lines    */
  13.  
  14. int  arr1[16], arr2[16];
  15. unsigned int arry[16384];
  16. int  binrule[KK][KK][KK], rule[NS];
  17. int  cy, cp, mc, nc, nl;
  18.  
  19. main() {
  20. int  i, i0, i1, i2;
  21.  
  22. printf("  t(totalistic) w(Wolfram) b(binary) \015");
  23. switch (kbdin()) {
  24.   case 't':
  25.     printf("\n\nRule number:\n\n");
  26.     printf("0..1\n");
  27.     for (i=0; i<NS; i++) rule[i]=kbdin()-'0';
  28.     printf("\n");
  29.     totobin();
  30.     break;
  31.   case 'w':                    /* Wolfram rule # */
  32.     printf("\n\n");
  33.     i=numin(0);
  34.     for (i0=0; i0<KK; i0++) {
  35.     for (i1=0; i1<KK; i1++) {
  36.     for (i2=0; i2<KK; i2++) {
  37.       binrule[i0][i1][i2]=i%2; i/=2;
  38.       };};};
  39.     break;
  40.   case 'b':
  41.     printf("\n\n");
  42.     printf("00001111\n");
  43.     printf("00110011\n");
  44.     printf("01010101\n");
  45.     i0=0; i1=0; i2=0;
  46.     for (i=0; i<8; i++) {
  47.     binrule[i0][i1][i2]=kbdin()-'0';
  48.     i2++;
  49.     if (i2>KK-1) {i2=0; i1++;};
  50.     if (i1>KK-1) {i1=0; i0++;};
  51.     if (i0>KK-1) {i0=0;};
  52.     };
  53.     printf("\n\n");
  54.     break;
  55.   }
  56.  
  57. nc=0;
  58. nl=0;
  59.  
  60. printf("Cycles of length 4"); kwait(0);
  61.  mc=7;
  62.  cy=4;
  63.  cp=16;
  64.  pass1();
  65.  pass2();
  66.  pass4();
  67.  
  68. printf("Cycles of length 5"); kwait(0);
  69.  mc=6;
  70.  cy=5;
  71.  cp=32;
  72.  pass1();
  73.  pass2();
  74.  pass4();
  75.  
  76. printf("Cycles of length 6"); kwait(0);
  77.  mc=5;
  78.  cy=6;
  79.  cp=64;
  80.  pass1();
  81.  pass2();
  82.  pass4();
  83.  
  84. printf("Cycles of length 7"); kwait(0);
  85.  mc=4;
  86.  cy=7;
  87.  cp=128;
  88.  pass1();
  89.  pass2();
  90.  pass4();
  91.  
  92. printf("Cycles of length 8"); kwait(0);
  93.  mc=4;
  94.  cy=8;
  95.  cp=256;
  96.  pass1();
  97.  pass2();
  98.  pass4();
  99.  
  100. printf("Cycles of length 9"); kwait(0);
  101.  mc=3;
  102.  cy=9;
  103.  cp=512;
  104.  pass1();
  105.  pass2();
  106.  pass4();
  107.  
  108. printf("Cycles of length 10"); kwait(0);
  109.  mc=3;
  110.  cy=10;
  111.  cp=1024;
  112.  pass1();
  113.  pass2();
  114.  pass4();
  115.  
  116. printf("Cycles of length 11"); kwait(0);
  117.  mc=3;
  118.  cy=11;
  119.  cp=2048;
  120.  pass1();
  121.  pass2();
  122.  pass4();
  123.  
  124. printf("Cycles of length 12"); kwait(0);
  125.  mc=2;
  126.  cy=12;
  127.  cp=4096;
  128.  pass1();
  129.  pass2();
  130.  pass4();
  131.  
  132. printf("Cycles of length 13"); kwait(0);
  133.  mc=2;
  134.  cy=13;
  135.  cp=8192;
  136.  pass1();
  137.  pass2();
  138.  pass4();
  139.  
  140. printf("Cycles of length 14"); kwait(0);
  141.  mc=2;
  142.  cy=14;
  143.  cp=16384;
  144.  pass1();
  145.  pass2();
  146.  pass4();
  147.  
  148. } /* end main */
  149.  
  150. /* Pass 1 makes arry[i] equal to the successor of i */
  151.  
  152. pass1() {int i, j, x;
  153.   printf(" Pass1\015");
  154.   for (j=0; j<cp; j++) {
  155.     x=j; for (i=0; i<cy; i++) {arr1[cy-i-1]=x%KK; x/=KK;};
  156.     evolve(cy);
  157.     x=0; for (i=0; i<cy; i++) x=KK*x+arr2[i]; arry[j]=x;
  158.   }; }
  159.  
  160. /* calculate one generation of evolution in a ring of length n */
  161.  
  162. evolve(n) int n; {
  163. int i;
  164.   arr2[0]=binrule[arr1[n-1]][arr1[0]][arr1[1]];
  165.   for (i=1; i<n-1; i++) arr2[i]=binrule[arr1[i-1]][arr1[i]][arr1[i+1]];
  166.   arr2[n-1]=binrule[arr1[n-2]][arr1[n-1]][arr1[0]];
  167. }
  168.  
  169. /* Pass 2 flags all links with an incoming arrow */
  170.  
  171. pass2() {int j, m, x;
  172. printf(" Pass2\015");
  173. do {
  174. m=0;
  175. for (j=0; j<cp; j++) arry[j]|=0x8000;
  176. for (j=0; j<cp; j++) {x=arry[j];
  177.  if (x!=0xFFFF) arry[x&0x7FFF]&=0x7FFF;};
  178. for (j=0; j<cp; j++) {
  179.  if ((arry[j]>0x7FFF) && (arry[j]!=0xFFFF)) {arry[j]=0xFFFF; m=1;};};
  180.  } while (m!=0);
  181. }
  182.  
  183. /* pass4 - print loops which remain */
  184.  
  185. pass4() {
  186. int j, x, y, m;
  187. printf(" pass4 \015");
  188. for (j=0; j<cp; j++) {
  189.  x=j; y=arry[j]; arry[j]=0xFFFF; m=0;
  190.  while (y!=0xFFFF) {prf(x,y); x=y; y=arry[x]; arry[x]=0xFFFF; m=1;};
  191.  if (m==1) kwait(0);
  192.  };
  193. }
  194.  
  195. /* change totalistic rule to general rule */
  196.  
  197. totobin() {
  198. int i0, i1, i2;
  199. for (i0=0; i0<KK; i0++) {
  200. for (i1=0; i1<KK; i1++) {
  201. for (i2=0; i2<KK; i2++) {
  202. binrule[i0][i1][i2]=rule[i0+i1+i2];
  203. };};};
  204. }
  205.  
  206. /* print the link */
  207.  
  208. prf(j,x) int j, x; {int i, y;
  209.   kwait(1);
  210.   y=j; for (i=0; i<cy; i++) {arr1[i]=y%KK; y/=KK;};
  211.   for (i=0; i<cy; i++) printf("%1d",arr1[i]);
  212.   printf("-");
  213.   y=x; for (i=0; i<cy; i++) {arr1[i]=y%KK; y/=KK;};
  214.   for (i=0; i<cy; i++) printf("%1d",arr1[i]);
  215.   printf("  ");
  216. }
  217.  
  218. /* print arry - for diagnostic purposes */
  219. pall() {int j;
  220. for (j=0; j<cp; j++) printf("%4d",arry[j]);
  221. }
  222.  
  223. /* print cycle - for diagnostic purposes */
  224. pcy() {int j;
  225. for (j=0; j<cy; j++) printf("%1d",arr2[j]);
  226. }
  227.  
  228. /* limit j to interval (i,k) */
  229. int lim(i,j,k) int i, j, k;
  230.     {if (i>=j) return i; if (k<=j) return k; return j;}
  231.  
  232. /* read number from keyboard */
  233. int numin(n) int n; {char c;
  234.   c=kbdin();
  235.   if (c>='0'&&c<='9') return(numin(10*n+(c-'0'))); else return(n);
  236. }
  237.  
  238. /* keyboard status */
  239. kbdst() {return bdos(11)&0xFF;}
  240.  
  241. /* direct keyboard input, no echo */
  242. kbdin() {int c;
  243. if ((c=bdos(7)&0xFF)=='\0') c=(bdos(7)&0xFF)|0x80;
  244. videoputc(c,1);
  245. return c;}
  246.  
  247. /* pause at the end of a full screen */
  248. /* kwait(0) - <cr><lf> and count it  */
  249. /* kwait(1) - count columns          */
  250.  
  251. kwait(i) int i; {
  252. switch (i) {
  253.   case 0: printf("\n"); nc=0; nl++; break;
  254.   case 1: if (nc==mc) {printf("&\n"); nc=1; nl++;} else nc++; break;
  255.   default: break;};
  256. if (nl==NW) {
  257.   nl=0;
  258.   printf(" press any key to continue\015");
  259.   while (kbdst()) {};
  260.   kbdin();
  261.   printf("-                         \n");
  262.   };
  263. }
  264.  
  265. /* end */
  266.